package review;



import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class TreeNode {
    int val;
   TreeNode left;
    TreeNode right;

    public void levelHelper(ArrayList<ArrayList<Integer>> list, TreeNode root, int level){
        if(root==null)
            return ;
        if(level>=list.size()){
            list.add(new ArrayList<>());
        }
        list.get(level).add(root.val);
        levelHelper(list,root.left,level+1);
        levelHelper(list,root.right,level+1);
    }
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        int level=0;
        levelHelper(list,root,level);
        return list;
    }


    public ArrayList<ArrayList<Integer>> levelOrder2(TreeNode root){
        if(root==null)
            return null;
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> temp=new ArrayList<>();
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                temp.add(node.val);
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(temp);
        }

        return list;
    }
    //左右顺序输出
    public  ArrayList<ArrayList<Integer>> levelOrder3(TreeNode root){
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        if(root!=null)
            queue.add(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> temp=new ArrayList<Integer>();
            for(int i=queue.size();i>0;i--){
                TreeNode node=queue.poll();
                if((list.size()+1)%2==1){
                    temp.add(node.val);
                }else{
                    temp.add(0,node.val);//倒插
                }
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(temp);
        }

        return list;
    }

    public ArrayList<ArrayList<Integer>> threeNum(int[] a){


        if(a.length<=3||a==null){
            return null;
        }
        Arrays.sort(a);
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        for(int i=0;i<a.length-2;i++){
            if(a[i]>0)
                break;
            if(i>0&&a[i]==a[i+1])
                continue;
            int left=i+1;
            int right=a.length-1;

            while(left<right){
                int sum=a[i]+a[left]+a[right];
                if(sum>0){
                    right--;
                }
                if(sum==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(a[i]);
                    list.add(a[i+1]);
                    list.add(a[right]);
                    res.add(list);
                    while(left<right&&a[left]==a[left+1])
                        left++;
                    while(left<right&&a[right]==a[right-1])
                        right--;
                    left++;right--;
                }
                if(sum<0){
                    left++;
                }
                left++;
                right--;
            }


        }
        return res;
    }
    public static void main(String[] args){
   /*     TreeNode node=new TreeNode();
        node.val=1;
        TreeNode left=new TreeNode();
        left.val=2;
        TreeNode right=new TreeNode();
        right.val=3;
        node.left=left;
        node.right=right;
        System.out.print(node.levelOrder2(node));
        System.out.println(node.levelOrder(node));
        System.out.println(node.levelOrder3(node));*/
        int[] a={-2,0,1,1,2};
        ArrayList<ArrayList<Integer>> list=new TreeNode().threeNum(a);
        System.out.println(list);
    }
}
